'''
数组可以说是最简单的一种数据结构，他占据一块连续的内存并按照顺序存储数据。
在C\C++中需要首先指定数组的容量大小，然后根据大小分配内存，数组的空间效率不是很好
总是会有空闲的区域没有得到充分的利用。
但是也因为数组的内存是连续的，因此他可以做到以O(1)的时间读写任何元素，因此其时间效率很高
'''


# 题目1:找出数组中的重复数字
# 在一个长度为n的数组里的所有数字都在0~n-1的范围内，数组中某些数字是重复的，但不知道有多少数字重复了，
# 也不知道每个数字重复了多少次，请找出数组中任意一个重复的数字。例如{2,3,1,0,2,5,3}中重复的数字是2，或者3

def duplicate_1(ls):
    length = len(ls)
    if length < 1:
        return False

    res = []
    for i in range(length):
        if ls[1] < 0 or ls[i] > length - 1:
            return False
        while ls[i] != i:
            if ls[i] == ls[ls[i]]:
                res.append(ls[i])
                break

            # swap ls[i] and ls[ls[i]]
            tmp = ls[i]

            ls[i] = ls[tmp]
            ls[tmp] = tmp
            print(ls)
    return res


# 题目二：不修改数组找出重复的数字
# 在一个长度为n+1的数组中的所有数字都在1~n中，所以数组中至少有一个数字是重复的，请找出数组中任意一个重复的数字，但不能修改数组

# 在这一问中书上给出的二分查找代码并不是十分好的找出所有重复的数字，而在python中有比较好的解决方法如字典，pythonic
def duplicate_2(ls):
    if len(ls) < 1:
        return None
    dic = dict()

    for i in range(len(ls)):
        if ls[i] < 0 or ls[i] > len(ls) - 1:
            return False
        tmp = ls[i]
        if tmp not in dic:
            dic[tmp] = 1
        else:
            dic[tmp] += 1
    res = [key for key in dic.keys() if dic[key] > 1]
    return res if len(res) > 0 else None


if __name__ == '__main__':
    ls = [3, 1, 2, 0, 2, 5, 3]
    ls1 = [2, 3, 5, 4, 3, 2, 6, 7]

    print(duplicate_1(ls))
    print(duplicate_1(ls1))

    print(duplicate_2(ls))
    print(duplicate_2(ls1))